\documentclass[a4paper]{article} 

\usepackage{listings}
\lstset{tabsize=4, %
	frame=shadowbox, %把代码用带有阴影的框圈起来
	commentstyle=\color{red!50!green!50!blue!50},%浅灰色的注释
	rulesepcolor=\color{red!20!green!20!blue!20},%代码块边框为淡青色
	keywordstyle=\color{blue!90}\bfseries, %代码关键字的颜色为蓝色，粗体
	showstringspaces=false,%不显示代码字符串中间的空格标记
	stringstyle=\ttfamily, % 代码字符串的特殊格式
	keepspaces=true, %
	breakindent=22pt, %
	numbers=left,%左侧显示行号
	stepnumber=1,%
	numberstyle=\tiny, %行号字体用小号
	basicstyle=\footnotesize, %
	showspaces=false, %
	flexiblecolumns=true, %
	breaklines=true, %对过长的代码自动换行
	breakautoindent=true,%
	breakindent=4em, %
	%escapebegin=\begin{CJK*}{GBK}{hei},escapeend=\end{CJK*},
	aboveskip=1em, %代码块边框
	fontadjust,
	captionpos=t,
	framextopmargin=2pt,framexbottommargin=2pt,
	abovecaptionskip=-3pt,belowcaptionskip=3pt,
	xleftmargin=4em,xrightmargin=4em, % 设定listing左右的空白
	texcl=true,
	% 设定中文冲突，断行，列模式，数学环境输入，listing数字的样式
	extendedchars=false,columns=flexible,mathescape=true
	% numbersep=-1em
}
\usepackage{cite}
\usepackage{fancyhdr}
\usepackage{lipsum}
\usepackage{extarrows}
\usepackage{ctex}
\usepackage{amsfonts,amssymb} 
\usepackage{amsmath} 
\usepackage{cases}
\usepackage{geometry}
\usepackage{graphicx}
\usepackage{listings}
\usepackage{xcolor}
\usepackage{framed}
\usepackage{float}
\usepackage{ulem}
\usepackage{booktabs}
\usepackage{amsthm}
\usepackage{tikz}
\usepackage{pgfplots}
\pgfplotsset{width=10cm,compat=1.9}
\geometry{a4paper,left=3cm,right=3cm,top=3cm,bottom=3cm}

\begin{document}
	\begin{center}
		{\heiti {\huge 第三次编程作业报告}}
	\end{center}
	
	\begin{center}
		{\large 求数2101\ 叶陈昊\ 3210106359}
	\end{center}
	
	\section{题目：计算器的实现}
	本题要求设计一个四则混合运算器，用户输入为一个字符串，
	忽略其中不属于数字，小数点， +， -， *， /， (，)
	（今后，将以上符号叫做表达式的“有效字符”）和空格以外的字符.
	将剩下的符号，识别成浮点数和运算符；
	如果这些浮点数(包括整数)和运算符组成合法的中缀表达式，输出其运算结果；
	如果无法组成合法的中缀表达式，输出“Error.”
	
	\section{设计思路}
	
	主要分为两个部分，即首先要将中缀表达式转化为后缀表达式，
	其次要将后缀表达式的值算出来.经过分析，我认为应当将“后缀表达式的计算”
	写到一个函数里，即传入一个队列，返回一个浮点数.在这个函数中是不应当有报错的
	（函数具有适配性，本题要求输出到指定文件中，因此不报错是最好的），
	我们要在第一步将中缀表达式转化成严格的后缀表达式.
	
	\subsection{将字符串转化为严格的后缀表达式}
	
	对于一个字符串，我们不用管有效字符之外的字符.
	今后，我们不妨假设输入的字符串里都是有效字符.
	
	首先，我们考虑一个很正常的中缀表达式，例如：$1/0.25+2*(3-4).$
	可以看到里面包含了基本的有效字符.我们考虑一个队列\texttt{exp}，
	用于存放相应的后缀表达式；一个堆栈\texttt{ops}，用于存放四则运算符和括号，
	具体如下实施：
	\begin{itemize}
		\item 浮点数的存储：当读到数字或小数点时，开始存放到队列\texttt{exp}中，
		      直到读到运算符为止.此时，为了间隔开每个浮点数，我们手动在\texttt{exp}
		      中放入一个空格.以后此字符串转化成浮点数的过程就可以利用这个空格来实现.
		\item 运算符的存储：注意到在中缀表达式中运算符的优先级是括号高于乘除高于加减，
			  而后缀表达式不需要括号，也不需要考虑优先级问题.
			  因此我们先将读取到的运算符存储到堆栈\texttt{ops}中，
			  再视优先级将运算符转移到\texttt{exp}中.\\
			  遇到左括号（最高优先级）时，入栈，等读到右括号时再清除；\\
			  遇到乘/除号时，将在栈顶部的同级运算符出栈转移到表达式队列中，
			  然后让自己入栈；\\
			  遇到加/减号（最低优先级）时，将在栈中的元素依次出栈（直到遇到左括号，
			  因为括号是最高优先级），然后让自己入栈.\\
			  当字符串被读完后，将\texttt{ops}中剩余的元素出栈.
			  
	\end{itemize}
	将这些规则应用到上例表达式，得：
	$1/0.25+2*(3-4)\rightarrow 1\ 0.25\ /2\ 3\ 4\ -\ *\ +$.
	
	现在，我们来考虑一些非法的中缀表达式（仍然忽略除有效字符外的字符），
	较常见的有以下情况：
	\begin{itemize}
		\item 多余的左/右括号：根据上述规则，若左括号多余，则会留在栈\texttt{ops}
			  中，报错可以在此地方设置；若右括号多余，则在表达式读取完毕
			  并将栈中元素清除完后发现仍然没有左括号匹配，报错可以在此设置.
		\item 空括号：只要括号内没有任何数字成分，它就可以被认为是一个空括号，
			  可借此设置报错条件.
		\item 多余的四则运算符：由于中缀表达式要求两个四则运算符之间一定要有
			  一个浮点数，因此可将其作为判断条件.
	    \item 多余的小数点：由于一个浮点数至多一个小数点，可将其作为判断条件.
	    \item 单个浮点数前跟着乘号或除号（指乘/除号前面啥都没有，或者紧跟一个左括号）：
	    	  没有任何数学意义，可报错.
	    \item 读到四则运算符后在读到右括号或回车键前再没有跟任何浮点数：
	    	  没有任何数学意义，可报错.
	\end{itemize}
	
	而有些情况比较特殊，有些认为合法，有些认为不合法.这里以我的经验作一个区分：
	\begin{itemize}
		\item 左括号前紧跟着浮点数（合法）：此情况默认二者之间隐藏了一个乘号，
			  且此运算的优先级更高（例：$2(3+4)\Leftrightarrow (2*(3+4))$）.
		\item 右括号后紧跟着浮点数（非法）：默认括号与数字相乘不能忽略乘号.
		\item 单个浮点数前跟着加号或减号（合法）：默认成该浮点数的正号或负号.
		\item 两个括号紧跟在一起，即第一个括号的右括号后紧跟第二个括号的左括号
			  （合法）：此情况默认二者之间隐藏了一个乘号，且此运算的优先级更高
			  （例：$(1+2)(3+4)\Leftrightarrow ((1+2)*(3+4))$）.  
	\end{itemize}
	
	至此，我们大致讨论完了可能报错的一些原因，以及如何判断一个中缀表达式是否合法.
	
	接下来我们来看看如何将其转化成“严格”的后缀表达式.其实，回顾上面的情况，
	我们看到有一个地方需要处理，那就是“单个浮点数前跟着加号或减号”（即正/负号问题）.
	为了方便理解，考虑一个简单中缀表达式：$-2$.当然其结果就是$-2$.根据上面的各种
	规则与情况分析，转化得到后缀表达式：$2\ -$.可以很明显地看到，这里少了个数字，
	否则仅凭"$2$"和"$-$"肯定不是一个严格后缀表达式.要想变也很简单，
	只要在“2”入队前把“0”入队就行.那么，对于这种的一般情况，都可以在浮点数入队前
	让一个“0”先入队.
	
	现在，总体上已经将一个合法的中缀表达式变成一个严格的后缀表达式了.
	
	\subsection{求后缀表达式的值}
	
	对于一个严格的后缀表达式队列，我们需要干两件事：
	\begin{itemize}
		\item 将队列中的浮点数字串转化为浮点数.由于之前将中缀表达式转化成后缀表达式时
			  人为添加了空格，所以我们读到队列数字时持续将其存入一个字符数组中，
			  等到读到空格时中断.接着，我们利用\texttt{iostream}里的一个函数
			  \texttt{atof}，将字符数组转化为真正的浮点数，并存入到
			  一个\texttt{double}型的栈\texttt{nums}中.这个栈理所应当只存放浮点数.
		\item 当读取到队列\texttt{exp}中的一个运算符时，需要将栈\texttt{nums}中的
			  顶部的两个元素取出，并按照读到的运算符进行运算，算完后将结果入栈
			  \texttt{nums}.
	\end{itemize}

	经过以上两步，我们就能算出该后缀表达式的值.
	
	\section{测试数据及说明}
	
	测试数据分为非法和合法两部分.非法的表达式会列出所有我在上述提到的非法情况，
	合法的表达式也会给出一些具有特殊合法性的算式供参考.
	
	\texttt{1((2} $\rightarrow$ \texttt{Error! Extra left bracket!}
	
	\texttt{3+4)} $\rightarrow$ \texttt{Error! Extra right bracket!}
	
	\texttt{()1+2} $\rightarrow$ \texttt{Error! Empty brackets!}
	
	\texttt{1+*3} $\rightarrow$ \texttt{Error! Extra '*'!}
	
	\texttt{1.22.3+1} $\rightarrow$ \texttt{Error! Extra decimal point!}
	
	\texttt{*3.14} $\rightarrow$ \texttt{Error! No number before '*' !}
	
	\texttt{(/3.14)} $\rightarrow$ 
	\texttt{Error! No number before '/' in the brackets!}
	
	\texttt{3/} $\rightarrow$ \texttt{Error! No number after '/' !}
	
	\texttt{(3-)+2} $\rightarrow$ 
	\texttt{Error! No number after '-' in the brackets!}
	
	\texttt{(3)2} $\rightarrow$
	\texttt{Error! Number cannot follow the right bracket!}
	
	\texttt{---1*+++2} $\rightarrow$ \texttt{Error! Extra '-'!}
	\texttt{//没有按CASIO计算器那样处理成正负号的形式正常计算}
	
	\texttt{1/0.25+2*(3-4)} $\rightarrow$ 
	\texttt{1 0.25 /2 3 4 - * +} $\rightarrow$ \texttt{2}
	
	\texttt{1.abc0+2*(3+4.0i)*5} $\rightarrow$
	\texttt{1.0 2 3 4.0 + *5 * +} $\rightarrow$ \texttt{71}
	
	\texttt{1.23sf4g6} $\rightarrow$ \texttt{1.2346}
	
	\texttt{1.2sdf3!!3-0.23} $\rightarrow$ 
	\texttt{1.233 0.23 -} $\rightarrow$ \texttt{1.003}
	
	\texttt{1t.y21*(3RR-4T+ 1s.s00)} $\rightarrow$
	\texttt{1.21 3 4 -1.00 + *} $\rightarrow$ 
	\texttt{0  //以上五行是正常表达式的计算，正常处理即可}
	
	\texttt{3(2)} $\rightarrow$
	\texttt{3 2  *} $\rightarrow$ \texttt{6}
	
	\texttt{+3(2)} $\rightarrow$
	\texttt{0 3 2  * +} $\rightarrow$ \texttt{6}
	
	\texttt{(-3)(-2)} $\rightarrow$
	\texttt{0 3 - 0 2 - *} $\rightarrow$ \texttt{6}
	
	\texttt{-3(-2)} $\rightarrow$ \texttt{0 3 0 2 - * -} $\rightarrow$ 
	\texttt{6 //以上四行为特殊表达式的计算，对于有正负号的浮点数，需要在队列中补'0'}
	
	\section{总结}
	
	本次四则运算器的设计基本上符合题目要求.在一些特殊表达式的合法性判断上，参考了
	\texttt{CASIO fx-991CN X}计算器的合法性判断.在测试的过程中，
	我们发现一个算式在计算器中合法：$ ---1*+++2 = -2 $，它将这些加减号都当作
	正负号处理了，相当于表达式$(-(-(-1)))*(+(+(+2)))$.不过个人对这种情况采取报错，
	因为在实际情况中这种表达式若不使用括号，则会产生看不懂的风险.一般地，我们只会在
	算式的开头不使用括号的写负数，而在后面的负数中均使用括号，例如：$-2*(-3)$.
	
\end{document}